package suanfadaolun;

public class module15 {

    public static int cut_rod(int[] p , int n ){

        if(n==0){
            return 0;
        }

        int q = 0;
        for (int i = 1;i<=n;i++){
            q = Math.max(q,p[i]+cut_rod(p,n-i));
        }
        return q;
    }

    public static void main(String[] args) {
        int[] p = new int[]{0,1,5,8,9,10,17,17,20,24,30};
        System.out.println(cut_rod(p,5));
    }

}
